import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。
 *
 * 给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
 *
 * 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
 *
 * 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
 * User: wangxin
 * Date: 2025-04-14
 * Time: 22:04
 */
public class Test2 {
    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if(n == 1){
            res.add(0);
            return res;
        }
        List<Integer>[] adj = new List[n];
        for(int i = 0;i < n;i++){
            adj[i] = new ArrayList<Integer>();
        }
        for(int[] edge:edges){
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        int[] parent = new int[n];
        Arrays.fill(parent,-1);
        int x = findLongestNode(0,parent,adj);
        int y = findLongestNode(x,parent,adj);
        List<Integer> path = new ArrayList<Integer>();
        parent[x] = -1;
        while(y != -1){
            path.add(y);
            y = parent[y];
        }
        int m = path.size();
        if(m % 2 == 0){
            res.add(path.get(m/2 - 1));
        }
        res.add(path.get(m/2));
        return res;
    }
    public static int findLongestNode(int u,int[] parent,List<Integer>[] adj){
        int n = adj.length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        boolean[] visit = new boolean[n];
        queue.offer(u);
        visit[u] = true;
        int node = -1;
        while(!queue.isEmpty()){
            int curr = queue.poll();
            node = curr;
            for(int v:adj[curr]){
                if(!visit[v]){
                    visit[v] = true;
                    parent[v] = curr;
                    queue.offer(v);
                }
            }
        }
        return node;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] edges = {{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}};
        List<Integer> res = findMinHeightTrees(n,edges);
    }
}
